package com.stu.collection;

import java.util.*;

/**
 * ArrayList和LinkedList详细对比演示
 * 涵盖：
 * - 底层数据结构差异
 * - 性能特点对比
 * - 使用场景分析
 * - 内存占用对比
 * - 线程安全性
 * 
 * @author 学习者
 * @version 1.0
 */
public class ArrayListVsLinkedList {
    
    private static final int TEST_SIZE = 100000;
    
    public static void main(String[] args) {
        System.out.println("=== ArrayList vs LinkedList 详细对比 ===");
        
        // 1. 基本特性对比
        demonstrateBasicCharacteristics();
        
        // 2. 性能测试对比
        performanceComparison();
        
        // 3. 内存占用分析
        memoryUsageAnalysis();
        
        // 4. 使用场景建议
        usageScenarios();
        
        // 5. 线程安全性演示
        threadSafetyDemo();
    }
    
    /**
     * 演示ArrayList和LinkedList的基本特性
     */
    private static void demonstrateBasicCharacteristics() {
        System.out.println("\n=== 基本特性对比 ===");
        
        // ArrayList演示
        System.out.println("\nArrayList特性：");
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("元素1");
        arrayList.add("元素2");
        arrayList.add("元素3");
        
        System.out.println("1. 底层数据结构：动态数组（Object[]）");
        System.out.println("2. 默认初始容量：10");
        System.out.println("3. 扩容机制：当前容量 * 1.5");
        System.out.println("4. 随机访问：支持，时间复杂度O(1)");
        System.out.println("5. 插入删除：中间位置需要移动元素，时间复杂度O(n)");
        System.out.println("6. 内存连续：是，缓存友好");
        
        // 演示ArrayList的随机访问
        System.out.println("\nArrayList随机访问演示：");
        System.out.println("arrayList.get(1) = " + arrayList.get(1));
        System.out.println("arrayList.set(1, \"修改后\") = " + arrayList.set(1, "修改后"));
        System.out.println("修改后的列表：" + arrayList);
        
        // LinkedList演示
        System.out.println("\nLinkedList特性：");
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("节点1");
        linkedList.add("节点2");
        linkedList.add("节点3");
        
        System.out.println("1. 底层数据结构：双向链表");
        System.out.println("2. 节点结构：包含data、prev、next指针");
        System.out.println("3. 扩容机制：无需扩容，动态分配");
        System.out.println("4. 随机访问：不支持，需要遍历，时间复杂度O(n)");
        System.out.println("5. 插入删除：任意位置都是O(1)（如果有节点引用）");
        System.out.println("6. 内存连续：否，节点分散在堆中");
        
        // 演示LinkedList的特有方法
        System.out.println("\nLinkedList特有方法演示：");
        linkedList.addFirst("头部节点");
        linkedList.addLast("尾部节点");
        System.out.println("添加头尾节点后：" + linkedList);
        
        System.out.println("获取头部：" + linkedList.getFirst());
        System.out.println("获取尾部：" + linkedList.getLast());
        
        System.out.println("移除头部：" + linkedList.removeFirst());
        System.out.println("移除尾部：" + linkedList.removeLast());
        System.out.println("移除后的列表：" + linkedList);
        
        // LinkedList作为栈和队列使用
        System.out.println("\nLinkedList作为栈使用：");
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(1); // 入栈
        stack.push(2);
        stack.push(3);
        System.out.println("栈内容：" + stack);
        System.out.println("出栈：" + stack.pop());
        System.out.println("栈顶元素：" + stack.peek());
        
        System.out.println("\nLinkedList作为队列使用：");
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("第一个"); // 入队
        queue.offer("第二个");
        queue.offer("第三个");
        System.out.println("队列内容：" + queue);
        System.out.println("出队：" + queue.poll());
        System.out.println("队首元素：" + queue.peek());
    }
    
    /**
     * 性能对比测试
     */
    private static void performanceComparison() {
        System.out.println("\n=== 性能对比测试 ===");
        
        // 1. 添加元素性能测试
        addPerformanceTest();
        
        // 2. 随机访问性能测试
        randomAccessTest();
        
        // 3. 插入元素性能测试
        insertPerformanceTest();
        
        // 4. 删除元素性能测试
        removePerformanceTest();
    }
    
    /**
     * 添加元素性能测试
     */
    private static void addPerformanceTest() {
        System.out.println("\n1. 添加元素性能测试（" + TEST_SIZE + "个元素）：");
        
        // ArrayList添加测试
        long startTime = System.currentTimeMillis();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < TEST_SIZE; i++) {
            arrayList.add(i);
        }
        long arrayListTime = System.currentTimeMillis() - startTime;
        
        // LinkedList添加测试
        startTime = System.currentTimeMillis();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < TEST_SIZE; i++) {
            linkedList.add(i);
        }
        long linkedListTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList尾部添加耗时：" + arrayListTime + "ms");
        System.out.println("LinkedList尾部添加耗时：" + linkedListTime + "ms");
        
        // 头部添加测试（小数据量，避免超时）
        int smallSize = 10000;
        System.out.println("\n头部添加性能测试（" + smallSize + "个元素）：");
        
        startTime = System.currentTimeMillis();
        List<Integer> arrayListHead = new ArrayList<>();
        for (int i = 0; i < smallSize; i++) {
            arrayListHead.add(0, i); // 头部插入
        }
        long arrayListHeadTime = System.currentTimeMillis() - startTime;
        
        startTime = System.currentTimeMillis();
        LinkedList<Integer> linkedListHead = new LinkedList<>();
        for (int i = 0; i < smallSize; i++) {
            linkedListHead.addFirst(i); // 头部插入
        }
        long linkedListHeadTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList头部添加耗时：" + arrayListHeadTime + "ms");
        System.out.println("LinkedList头部添加耗时：" + linkedListHeadTime + "ms");
        
        System.out.println("\n分析：");
        System.out.println("- 尾部添加：ArrayList和LinkedList性能相近");
        System.out.println("- 头部添加：LinkedList明显优于ArrayList");
        System.out.println("- ArrayList头部插入需要移动所有元素，时间复杂度O(n)");
        System.out.println("- LinkedList头部插入只需要修改指针，时间复杂度O(1)");
    }
    
    /**
     * 随机访问性能测试
     */
    private static void randomAccessTest() {
        System.out.println("\n2. 随机访问性能测试：");
        
        // 准备测试数据
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        for (int i = 0; i < TEST_SIZE; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        // ArrayList随机访问测试
        long startTime = System.currentTimeMillis();
        Random random = new Random();
        for (int i = 0; i < 10000; i++) {
            int index = random.nextInt(TEST_SIZE);
            arrayList.get(index);
        }
        long arrayListTime = System.currentTimeMillis() - startTime;
        
        // LinkedList随机访问测试
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            int index = random.nextInt(TEST_SIZE);
            linkedList.get(index);
        }
        long linkedListTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList随机访问10000次耗时：" + arrayListTime + "ms");
        System.out.println("LinkedList随机访问10000次耗时：" + linkedListTime + "ms");
        
        System.out.println("\n分析：");
        System.out.println("- ArrayList：数组结构，支持随机访问，时间复杂度O(1)");
        System.out.println("- LinkedList：链表结构，需要遍历到指定位置，时间复杂度O(n)");
        System.out.println("- 频繁随机访问场景，ArrayList性能远优于LinkedList");
    }
    
    /**
     * 插入元素性能测试
     */
    private static void insertPerformanceTest() {
        System.out.println("\n3. 中间位置插入性能测试：");
        
        int insertSize = 1000;
        
        // ArrayList中间插入测试
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < insertSize; i++) {
            arrayList.add(i);
        }
        
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < insertSize; i++) {
            arrayList.add(arrayList.size() / 2, i); // 中间位置插入
        }
        long arrayListTime = System.currentTimeMillis() - startTime;
        
        // LinkedList中间插入测试
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < insertSize; i++) {
            linkedList.add(i);
        }
        
        startTime = System.currentTimeMillis();
        for (int i = 0; i < insertSize; i++) {
            linkedList.add(linkedList.size() / 2, i); // 中间位置插入
        }
        long linkedListTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList中间插入" + insertSize + "次耗时：" + arrayListTime + "ms");
        System.out.println("LinkedList中间插入" + insertSize + "次耗时：" + linkedListTime + "ms");
        
        System.out.println("\n分析：");
        System.out.println("- ArrayList中间插入：需要移动插入位置后的所有元素");
        System.out.println("- LinkedList中间插入：需要先遍历到插入位置，然后修改指针");
        System.out.println("- 对于中间位置插入，性能差异取决于数据量和插入位置");
    }
    
    /**
     * 删除元素性能测试
     */
    private static void removePerformanceTest() {
        System.out.println("\n4. 删除元素性能测试：");
        
        int removeSize = 1000;
        
        // ArrayList删除测试
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < removeSize * 2; i++) {
            arrayList.add(i);
        }
        
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < removeSize; i++) {
            arrayList.remove(arrayList.size() / 2); // 中间位置删除
        }
        long arrayListTime = System.currentTimeMillis() - startTime;
        
        // LinkedList删除测试
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < removeSize * 2; i++) {
            linkedList.add(i);
        }
        
        startTime = System.currentTimeMillis();
        for (int i = 0; i < removeSize; i++) {
            linkedList.remove(linkedList.size() / 2); // 中间位置删除
        }
        long linkedListTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList中间删除" + removeSize + "次耗时：" + arrayListTime + "ms");
        System.out.println("LinkedList中间删除" + removeSize + "次耗时：" + linkedListTime + "ms");
        
        System.out.println("\n分析：");
        System.out.println("- ArrayList删除：需要移动删除位置后的所有元素");
        System.out.println("- LinkedList删除：需要先遍历到删除位置，然后修改指针");
        System.out.println("- 头尾删除LinkedList更优，中间删除性能相近");
    }
    
    /**
     * 内存占用分析
     */
    private static void memoryUsageAnalysis() {
        System.out.println("\n=== 内存占用分析 ===");
        
        System.out.println("\nArrayList内存特点：");
        System.out.println("1. 存储结构：连续的数组空间");
        System.out.println("2. 额外开销：数组容量通常大于实际元素数量");
        System.out.println("3. 内存局部性：好，缓存友好");
        System.out.println("4. 空间复杂度：O(n)");
        
        System.out.println("\nLinkedList内存特点：");
        System.out.println("1. 存储结构：分散的节点，每个节点包含数据和两个指针");
        System.out.println("2. 额外开销：每个节点需要额外的prev和next指针（8字节 * 2）");
        System.out.println("3. 内存局部性：差，节点分散在堆中");
        System.out.println("4. 空间复杂度：O(n)，但常数因子更大");
        
        // 简单的内存使用演示
        System.out.println("\n内存使用示例分析：");
        System.out.println("假设存储1000个Integer对象：");
        System.out.println("ArrayList：");
        System.out.println("  - 数组：1000 * 4字节（引用） = 4KB");
        System.out.println("  - 扩容预留：通常会有额外25%-50%空间");
        System.out.println("  - 总计：约5-6KB（不包括Integer对象本身）");
        
        System.out.println("LinkedList：");
        System.out.println("  - 节点：1000 * (4字节数据 + 8字节prev + 8字节next) = 20KB");
        System.out.println("  - 对象头：1000 * 8字节 = 8KB");
        System.out.println("  - 总计：约28KB（不包括Integer对象本身）");
        
        System.out.println("\n结论：LinkedList的内存开销约为ArrayList的4-5倍");
    }
    
    /**
     * 使用场景建议
     */
    private static void usageScenarios() {
        System.out.println("\n=== 使用场景建议 ===");
        
        System.out.println("\n选择ArrayList的场景：");
        System.out.println("1. 频繁随机访问元素（通过索引）");
        System.out.println("2. 主要在尾部添加/删除元素");
        System.out.println("3. 内存敏感的应用（LinkedList内存开销大）");
        System.out.println("4. 需要利用CPU缓存的场景");
        System.out.println("5. 遍历操作较多的场景");
        System.out.println("6. 数据量较大且访问模式相对固定");
        
        System.out.println("\n选择LinkedList的场景：");
        System.out.println("1. 频繁在头部或中间插入/删除元素");
        System.out.println("2. 不需要随机访问，主要是顺序访问");
        System.out.println("3. 需要实现栈或队列功能");
        System.out.println("4. 数据量不确定，需要动态增长");
        System.out.println("5. 插入删除操作远多于查询操作");
        
        System.out.println("\n性能总结：");
        System.out.println("操作类型\t\tArrayList\t\tLinkedList");
        System.out.println("随机访问\t\tO(1)\t\t\tO(n)");
        System.out.println("尾部添加\t\tO(1)*\t\t\tO(1)");
        System.out.println("头部添加\t\tO(n)\t\t\tO(1)");
        System.out.println("中间插入\t\tO(n)\t\t\tO(n)");
        System.out.println("删除元素\t\tO(n)\t\t\tO(n)");
        System.out.println("内存占用\t\t较少\t\t\t较多");
        System.out.println("缓存友好\t\t是\t\t\t否");
        
        System.out.println("\n注：ArrayList尾部添加在需要扩容时为O(n)");
    }
    
    /**
     * 线程安全性演示
     */
    private static void threadSafetyDemo() {
        System.out.println("\n=== 线程安全性演示 ===");
        
        System.out.println("\nArrayList和LinkedList都不是线程安全的");
        System.out.println("在多线程环境下使用需要额外的同步措施：");
        
        // 1. 使用Collections.synchronizedList
        List<String> syncArrayList = Collections.synchronizedList(new ArrayList<>());
        List<String> syncLinkedList = Collections.synchronizedList(new LinkedList<>());
        
        System.out.println("\n1. 使用Collections.synchronizedList：");
        System.out.println("List<String> syncList = Collections.synchronizedList(new ArrayList<>());");
        System.out.println("特点：每个方法都加了synchronized，性能较差");
        
        // 2. 使用Vector（ArrayList的线程安全版本）
        Vector<String> vector = new Vector<>();
        System.out.println("\n2. 使用Vector（ArrayList的线程安全替代）：");
        System.out.println("Vector<String> vector = new Vector<>();");
        System.out.println("特点：方法级别的synchronized，性能较差");
        
        // 3. 使用CopyOnWriteArrayList
        System.out.println("\n3. 使用CopyOnWriteArrayList（读多写少场景）：");
        System.out.println("List<String> cowList = new CopyOnWriteArrayList<>();");
        System.out.println("特点：写时复制，读操作无锁，适合读多写少");
        
        // 4. 手动同步
        System.out.println("\n4. 手动同步：");
        System.out.println("synchronized(list) {");
        System.out.println("    // 对list的操作");
        System.out.println("}");
        System.out.println("特点：灵活控制同步粒度，但容易出错");
        
        // 5. 使用并发集合
        System.out.println("\n5. 推荐使用java.util.concurrent包下的并发集合：");
        System.out.println("- ConcurrentLinkedQueue：高性能并发队列");
        System.out.println("- ConcurrentLinkedDeque：高性能并发双端队列");
        System.out.println("- BlockingQueue实现：ArrayBlockingQueue、LinkedBlockingQueue等");
        
        System.out.println("\n线程安全选择建议：");
        System.out.println("- 读多写少：CopyOnWriteArrayList");
        System.out.println("- 队列操作：ConcurrentLinkedQueue");
        System.out.println("- 生产者消费者：BlockingQueue实现");
        System.out.println("- 简单同步：Collections.synchronizedList + 外部同步");
    }
}